The present invention relates to a compiler technique, and particularly relates to inlining which is a compiler optimization technique.
Inlining is also referred to as inline expansion or inline function expansion, and is one of most important optimization techniques for compilers. Inlining is a technique in which optimization is achieved by expanding code for a function called by a function caller and preventing control from being transferred to the function.
Function inlining is performed by inserting a directive, such as an inline keyword, into source code during coding.
For example, inlining can (1) reduce overhead associated with calls and returns, (2) expand the range of compiler optimization, and (3) improve spatial locality of code. Inlining is particularly effective for functions which are small and frequently called.
By default, a compiler can automatically determine whether code is to be inline-expanded.
Japanese Patent Application Publication No. 6-202875 describes a compiler that performs optimization through inline expansion. The compiler includes control flow weighting means for estimating the number of executions of each partial control flow included in a control flow on the basis of a result of analysis by control flow analyzing means, and weighting each partial control flow on the basis of the number of executions; and object generating means for determining, with reference to a result of the weighting performed by the control flow weighting means, the necessity of inline expansion of a function called by each function call, and generating an object program reflecting the determination.
Japanese Patent Application Publication No. 11-212797 describes a program converting method for converting a source program written in a programming language to an object program written in a language executable by a computer or processor, characterized in that the object program is generated by changing indirect calling code to direct calling code, wherein, in the indirect calling code, on the basis of information about a procedure, function, or subroutine obtained in the process of converting the source program to the object program, identification information of the procedure, function, or subroutine is assigned to a specific variable at a point in a program, and the procedure, function, or subroutine is indirectly called by using the variable at another point, whereas in the direct calling code, the procedure, function, or subroutine is directly called at a point in the program.
Japanese Patent Application Publication No. 2001-188681 describes an inline expansion method that includes the steps of translating source code into object code without inline-expanding at least some of functions included in the source code; selectively changing the object code; executing the object code and measuring the number of calls and the processing time of the at least some of the functions; and selectively inline-expanding the at least some of the functions included in the source code with reference to the number of calls and the processing time.
Japanese Patent Application Publication No. 11-306026 describes a code optimization method related to a CPU having a plurality of instruction sets. The code optimization method includes a cost calculating step of calculating a cost of program code to be optimized on the basis of a cost evaluation table, and storing a result of the calculation; and an optimization-instruction-set selecting step of selecting an optimum instruction set from the stored result of the calculation. In this code optimization method, the cost calculating step inline-expands the program code, calculates a cost of the inline-expanded program code on the basis of the cost evaluation table, and stores a result of the calculation.
Japanese Patent Application Publication No. 2004-62234 describes a compile program running on a computer and converting a source program including a function call to object code. In the compile program, if a function to be inline-expanded is called from the same function at a plurality of points, expansion code for the callee function is shared by using a branch instruction from the call points.
D. R. Chakrabarti and S. Liu, “Inline Analysis: Beyond Selection Heuristics”, Proceedings of the International Symposium on Code Generation and Optimization, pages 221-232, 2006; O. Beohm, D. Citron, G. Harber, M. Klausner, and R. Levin, “IBM Research Report, Aggressive Function Inlining with Global Code Reordering”, Computer Science, H-0247 (H0611-009), Nov. 15, 2006; P. P. Chang and W. W. Hwu, “Inline function expansion for compiling C programs”, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, pages 246-257, 1989; and P. P. Chang, S. A. Mahlke, W. Y. Chen, and W. W. Hwu, “Profile-guided automatic inline expansion for C programs”, Software Practice and Experience”, Vol. 22(5), pages 349-369, May 1992, each describe an inlining technique for static compilers.
J. Cavazos and M. F. P. O'Boyle, “Automatic Tuning of Inlining Heuristics”, Proceedings of the 2005 ACM/IEEE SC Conference, page 14, November 2005; K. Hazelwood and D. Grove, “Adaptive Online Context-Sensitive Inlining”, Proceedings of the international symposium on Code generation and optimization”, feedback-directed and runtime optimization, pages 253-264, 2003; M. Arnold, S. Fink, V. Sarkar, and P. Sweeney, “A comparative study of static and dynamic heuristics for inlining”, ACM SIGPLAN Workshop on Dynamic and Adaptive Compilation and Optimization, 2000; S. Kulkarni, J. Cavazos, C. Wimmer, and D. Simon, “Automatic construction of inlining heuristics using machine learning”, Proceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization, 2013; and T. Suganuma, T. Yasue, M. Kawahito, H. Komatsu, and T. Nakatani, “Design and Evaluation of Dynamic Optimizations for a Java Just-In-Time Compiler”, ACM Transactions on Programming Languages and Systems, Vol. 27, No. 4, pages 732-785, July 2005 each describe an inlining technique for dynamic compilers.
P. Zhao and J. N. Amaral, “To Inline or Not to Inline? Enhanced Inlining Decision”, 16th Workshop on Languages and Compilers for Parallel Computing, 2003 describes an inlining technique based on temperature heuristics.